「ZJOI2019模拟赛 十二」紫苑

发表于 | 分类于 | | 浏览量： 次

震惊！XZY竟然在ZJOI模拟赛时公然写代码造数据卡掉各种排序算法…

传送门

原题来自UOJ，但各个子任务的分值略有不同。

UOJ83

题解

这题是真的毒瘤QwQ。

Subtask #1

观察一下计数排序法的代码，发现它在排序开始之前先把数组从$0$到$max(A_i)$清了一遍，那么只要给一个数，并且足够大即可。简直就是送分。

Subtask #2

从第二个子任务开始，题目渐渐地毒瘤了起来。

首先你需要知道对于冒泡排序法，交换元素的次数等于逆序对的个数。

然后仔细分析代码，计算出冒泡排序法和计数排序法的具体复杂度，然后发现，只要构造一个长度为$1990​$的升序排列，然后选出$521​$对元素两两交换即可。此时冒泡刚好不会T，选排刚好T掉。

Subtask #3

继续分析代码。发现快排没有随机化，那么就让每次选的基准数都是整个序列的最大或者最小值，然后手动二分得到$n​$的值应该为$1984​$。

Subtask #4

对于冒泡排序法来说，一个降序的排列逆序对数最多，最容易T，但是对计数排序法就很不友好了。

然后再随便写几个数列试试看，发现类似于这样的序列很不错：2 2 2 1 1 1 0 0 0，手动多试几次值域和每个值出现的次数，就把这个点搞掉了。

Subtask #5

和子任务4一样是要卡冒泡，同样构造一个类似的序列，然后手动胡乱修改几个数的出现次数，然后就过了。（大雾

Subtask #6

woc最恶心的一个点，一定要好好分析一下随机排序法的代码。

首先发现随机函数是手写的，想到这里应该有玄机，赶紧仔细看看。

发现seed、RNG_a、RNG_b的初值都是一个奇怪的数字，在10进制下看不出啥玩意，打开计算器，转到二进制下看看。

然后发现RNG_a在二进制下是$1100101101010000000000001$，RNG_b是$100110100100000000000001$，后面都有一长串$0$和一个$1$。并且打乱数组时都是取随机值然后模$n$，然后想到如果$n$是$2$的正整数次幂的话就会有一些奇妙的性质：上面两个数字在模$n$意义下都等于$1​$。

考虑到最好应该让该程序打乱一遍数组就排序好，并且题目中时间上限给的十分准确，枚举$n$，发现$n=4096$时计时器的值刚好是$43026$，由此根据出题人心理学套路断定$n$一定等于$4096$。

然后再仔细观察，发现如果seed是一个确定的值，原序列各元素之间的大小关系可以确定。于是乎再枚举seed，发现$seed=2048$（模$n$的意义下）时倒推得到的原序列使得快排T掉了。可得$seed=2048$。

但是由于seed是一个根据输入序列生成的值，所以在确定原序列各元素之间的大小关系的情况下，关键在于如何构造一个合法的序列使得$seed=2048$。

所以可以先构造一个各元素值都尽量小的排列$A$，然后将所有大于$A[n]$的元素的值都加上个比如$10^6$，然后就可枚举$A[n]$，一点点把它的值变大，直到$seed=2048$。这样最后一个点就构造好了。

然后恭喜你获得荣誉勋章：毒瘤出题人。

代码

Subtask #1

1
//没有QwQ，手造

Subtask #2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<cstdio>
#include<algorithm>
using namespace std;
int n,A[2000];
int main()
{
	n=1990;
	printf("%d\n",n);
	for(int i=1;i<=n;i++) A[i]=i;
	for(int i=1;i<=521;i++) swap(A[i*2],A[i*2-1]);
	for(int i=1;i<=n;i++)
		printf("%d%c",A[i],i==n?'\n':' ');
	return 0;
}

Subtask #3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<cstdio>
#include<algorithm>
using namespace std;
int n,A[5000],counter;
int main()
{
	n=1984;
	printf("%d\n",n);
	for(int i=1;i<=n;i++) A[i]=i;
	for(int i=1;i<=n;i++)
	{
		int j=(i+1)/2;
		swap(A[i],A[j]);
	}
	for(int i=1;i<=n;i++)
		printf("%d%c",A[i],i==n?'\n':' ');
	return 0;
}

Subtask #4

其实后面少了几个0，可以手动补上，不补也没关系。

1
2
3
4
5
6
7
8
9
10
#include<cstdio>
using namespace std;
int main()
{
	printf("%d\n",1012);
	for(int i=30;i>=0;i--)
		for(int j=1;j<=32;j++)
			printf("%d ",i);
	return 0;
}

Subtask #5

用这个代码生成数据后还有手动乱搞一下QwQ。

1
2
3
4
5
6
7
8
9
10
#include<cstdio>
using namespace std;
int main()
{
	printf("%d\n",1015);
	for(int i=27;i>=0;i--)
		for(int j=1;j<=40;j++)
			printf("%d ",i);
	return 0;
}

Subtask #6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<cstdio>
#include<algorithm>
using namespace std;
int n,A[5000],counter;unsigned int seed,RNG_a,RNG_b;
void RNG_init()
{
	counter++;
	seed = 2166136261u;
	counter++;
	RNG_a = 26648577u;
	counter++;
	RNG_b = 10108929u;
}
int main()
{
	freopen("Shion.in","wb",stdout);
	n=4096;seed=2166136261u;
	printf("%d\n",n);
	for(int i=1;i<=n;i++) A[i]=i;
	for(int i=n;i;i--)
	{
		int j=(i+2048)%4096+1;
		swap(A[i],A[j]);
	}
	for(int i=1;i<=n;i++)
		if(A[i]>A[n])
			A[i]+=1000000;
	for(int i=1;i<n;i++)
		seed=(seed*16777619u)^A[i];
	while(((seed*16777619u)^A[n])%(unsigned int)4096!=(unsigned int)2048) A[n]++;
	for(int i=1;i<=n;i++)
		printf("%d%c",A[i],i==n?'\n':' ');
	return 0;
}

答案

戳我呀^w^

终于写完了QwQ，出题人真是毒瘤QwQ。